The next generation of optical disks is known as digital-versatile disk (DVD). The CD-ROM drives on laptop and desktop PCs soon will be replaced with DVD drives. DVD has a much higher storage capacity than CD-ROM, enough that an entire motion picture can fit on a single DVD disk.
The large amount of data read during playback and the low-cost reproduction methods of optical disks increases the likelihood of encountering at least some errors on playback. Error detection and correction is thus important for CD-ROM's and DVD's. Smaller amounts of data such as stored in dynamic RAM memory often use parity--a bit is added to each data word so that the expanded word always has even or odd parity. Data from CD's and DVD's are arranged into larger blocks that have error-correction information appended. Multiple error-correction bytes allow errors to not only be detected, but also located and corrected. FIG. 1 illustrates a DVD data block with error correction for both rows and columns. Data from DVD disk 18 is read sequentially and stored in a block of data. As the data is read from DVD disk 18, it begins filling row 0 with data bytes 1, 2, 3 . . . until 182 bytes have been read. Error-correction information (ECC) for row 0 is contained in the last ten bytes of the row. Data from DVD disk 18 then begins filling the second row (row 1) with data bytes 173, 174, etc. until a second row of 172 data bytes and 10 ECC bytes has been transferred. Additional ECC bytes for the second row are contained in the last 10 bytes of row 1.
Subsequent rows of data and row-ECC information are read from DVD disk 18 and stored in a buffer memory block until all 192 rows of data have been transferred. Finally, sixteen rows of ECC bytes are read. ECC bytes in the final 16 rows are error-correction bytes for columns of data. For example, the first ECC byte in each of the last 16 rows is for column 0, which includes data byte 1 from row 0, data byte 173 from row 1, . . . , and data byte 32853 for data row 191, a total of 192 data bytes, each from a different row.
The final ten bytes of each row in the final 16 rows contains ECC information for the final 16 rows of column ECC bytes. This ensures that errors in the column ECC bytes can be detected and corrected.
Row and Column ECC
The ECC bytes at the end of a row can be used to detect, locate, and correct one or more errors within the row, but do not contain information on errors in other rows. Sometimes errors are too numerous to be detected or corrected in a row. Then the column ECC bytes can be used to find and correct the errors that are uncorrectable by the row ECC bytes. The ECC bytes at the bottom of a column are used to detect, locate, and correct one or more errors within the column, but do not contain information on errors in other columns. Column ECC provides a redundancy to error correction, allowing more difficult errors to be corrected.
Often the data and ECC bytes from the DVD disk are stored in a temporary buffer such as a static RAM buffer. Rows and columns are read to generate syndromes for each row and for each column. Syndromes are signatures or checksums formed by using a pre-defined mathematical operator on all data bytes and ECC bytes of a row or column. Polynomial operators are often used.
The syndromes are then compared to a pre-defined signature of zero to detect any errors in the row or column. The syndromes are also used to locate and correct a detected error. Complex algorithms such those based on Reed-Solomon code are used with the ECC bytes as is well-known in the art.
Multi-Byte Fetch for Row-Syndrome Generation--FIG. 2
FIG. 2 highlights that multiple bytes can be fetched from buffer memory for row syndrome generation. A syndrome for a row is generated by "summing" all the data and ECC bytes for a row. This "summing" is not a standard addition, but rather a complex signature-generating operation of scaling and adding the 182 bytes in a row. Multiple cycles can be used, such as by adding one byte per cycle to a running scaled sum.
Syndrome generator 10 performs the signature-generating operation as the bytes from the row are input. The buffer memory containing the data block often can read out multiple bytes per cycle. Thus FIG. 2 shows four-byte reads. In a first cycle, bytes 1, 2, 3, 4 are read from the buffer memory and operated on by syndrome generator 10. In a next memory cycle, data bytes 5, 6, 7, 8 are read from memory and accumulated by syndrome generator 10, adjusting the syndrome. Each successive memory cycle can read four bytes at once when the buffer memory is a standard 32-bit memory.
Once all 172 data bytes have been read and accumulated by syndrome generator 10, then the final 10 ECC bytes are read and accumulated. The final accumulated value in syndrome generator 10 is the row syndrome for the current row. Once the row syndrome is latched, syndrome generator 10 is cleared and the process repeated for next row.
Column Syndrome Generation--FIG. 3
FIG. 3 highlights column-syndrome generation. For column-syndrome generation, all of the bytes in a column are fetched from the buffer memory and input to syndrome generator 10. Only one byte from each row is needed. For column 0, byte 1 of row 0 is 1 fetched and input to syndrome generator 10. Since four bytes are always read, bytes 2, 3, 4 are also read, but not needed.
In the following memory cycle, data byte 173 is read from row 1, along with bytes 174, 175, 176. Only byte 173 is input to syndrome generator 10; fetched bytes 174, 175, 176 are discarded. For each succeeding row, one byte (at column 0) is read and input to syndrome generator 10, while three bytes are fetched and discarded (for columns 1, 2, 3).
Finally the last data byte 32,853 is read from row 191. Then during the next 16 memory cycles the 16 ECC bytes for column 0 are read and input to syndrome generator 10. After the last ECC byte has been read and accumulated by syndrome generator 10, the output from syndrome generator 10 is the column syndrome for column 0. The column syndrome can be latched, syndrome generator 10 cleared, and the process repeated for the second column. Then the second byte is input to syndrome generator 10 and the first, third, and fourth bytes discarded from each 4-byte fetch.
A total of 208 memory access cycles are required to fetch one byte from each of the 208 rows for column-syndrome generation. Using moderately wider fetches does not help, since adjacent bytes in a column are 182 bytes apart in the physical memory, separated by an entire row.
On-The-Fly ECC with SRAM Buffer--FIG. 4
FIG. 4 shows a prior-art optical-disk controller that uses a fast SRAM buffer for error correction. Error correction occurs "on-the-fly" as the data is read off optical disk 18 so that the data is corrected before being written to DRAM host buffer 64. Data read from optical disk 18 is first written to static-RAM buffer 60. Rows and columns of data are read from SRAM buffer 60 by error corrector 62 to generate row and column syndromes. When non-zero syndromes are found, the location and value of errors in a row are calculated and a read-modify-write cycle used to update the data in SRAM buffer 60 with the correction. Once all corrections are made, the corrected data in SRAM buffer 60 is moved to host-buffer 64. Host buffer 64 is a larger DRAM memory that can hold several blocks of data for transfer to the host.
SRAM buffer 60 is a much higher-speed memory than DRAM host buffer 64, allowing error corrector 62 to rapidly read and write the data being corrected. However, the higher cost of SRAM memory places limits on the size of SRAM buffer 60, so that only one or a few blocks can be present in SRAM buffer 60 at any time. DRAM host buffer 64 is much larger in size than SRAM buffer 60, allowing many corrected blocks to be buffered to the host at any time. Conventional DRAM memories have a limited bandwidth that is typically insufficient for instant error correction as the data is read from optical disk 18.
Many Reads and Writes for Error Correction--FIG. 5
FIG. 5 highlights that many reads and writes may occur during error correction. SRAM buffer 60 has a fast access time, allowing several reads and writes to occur during the time that one DRAM read occurs. Thus SRAM buffer 60 has a high bandwidth by virtue of the fast access time of static memories.
Data read from optical disk 18 is written to SRAM buffer 60. Once a row of an ECC block has been written, row syndrome generator 70 reads the data and ECC bytes in the row, and generates row-syndrome bytes. These row syndrome bytes can be written back to SRAM buffer 60, or put into a temporary latch and sent to row ECC calculator 72. Row ECC calculator 72 compares the row syndrome bytes to zero to detect errors in the row. When an error is detected, row ECC calculator 72 locates the error within the row and determines the error value. The error value is exclusive-OR'ed with the data in the row to correct the error. Row ECC calculator 72 performs a read-modify-write cycle to read the incorrect data from the row in SRAM buffer 60, XOR the error value to generate the corrected data, and then write the corrected data back into SRAM buffer 60.
Once row corrections are made for all rows in the ECC block, column syndromes are generated and column corrections made. Column syndrome generator 74 reads a column byte from each of the rows in SRAM buffer 60 and generates the column syndrome. The column syndrome is sent to column ECC calculator 76, which compares the column syndrome bytes to zero to detect errors in the column. When an error is detected, column ECC calculator 76 locates the error within the column and determines the error value. The error value is exclusive-OR'ed with the data in the column to correct the error. Column ECC calculator 76 performs a read-modify-write cycle to read the incorrect data from the column in SRAM buffer 60, XOR the error value to generate the corrected data, and then write the corrected data back into SRAM buffer 60.
Finally the corrected data is read and sent to the DRAM host buffer to make room for new data from optical disk 18. Each data and ECC byte is written at least once to SRAM buffer 60 and read at least three times--for the row and column syndromes, and for transfer to the host buffer. An additional read and write occur for every error. Thus from 1-3 writes and 3-5 reads can occur for any byte. This high bandwidth requirement has led designers to use expensive SRAM buffers for on-the-fly error correction.
While such SRAM buffers are effective, they add expense and complexity to optical-disk controllers. There is some redundancy to having both an SRAM and a DRAM buffer. This redundancy is wasteful. The alternative of using just a DRAM buffer may stall the reading of the optical disk while error correction occurs, slowing performance.
What is desired is a high-speed optical-disk playback system. It is desired to perform error correction or detection as quickly as possible, so that error correction does not force the disk to stall while error correction occurs. A virtual on-the-fly error corrector is desired that does not use an expensive SRAM buffer. It is desired to use a DRAM buffer for error correction. It is further desired to reduce bandwidth requirements for error correction to improve the performance of the error correction. A more efficient row syndrome-generation system is desired. It is desired to improve performance of row syndrome generation.